package main

import (
	"fmt"
	"leetcode/21/solution"
	"math/rand"
	"sort"
	"time"
)

// 21题
// 合并两个有序链表
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

func main() {
	var (
		l1 = createLinked(0, 10)
		l2 = createLinked(20, 50)
	)

	// 方案1
	fmt.Println(checkLinked(solution.V1(l1, l2)))

	// 方案2
	fmt.Println(checkLinked(solution.V2(l1, l2)))
}

// 验证链表
func checkLinked(linked *solution.ListNode) []int {
	rst := make([]int, 0)

	for linked != nil {
		rst = append(rst, linked.Val)

		linked = linked.Next
	}

	return rst
}

// 创建链表
func createLinked(num uint, seed int64) *solution.ListNode {
	var (
		linked *solution.ListNode
		prev   *solution.ListNode
		arr    = make([]int, 0)
		val    int
	)

	rand.Seed(seed + time.Now().UnixNano())

	for num > 0 {
		val = rand.Intn(100) + 1
		arr = append(arr, val)
		num--
	}

	sort.Ints(arr)

	for _, v := range arr {
		if prev == nil {
			linked = &solution.ListNode{Val: v}
			prev = linked
		} else {
			prev.Next = &solution.ListNode{Val: v}
			prev = prev.Next
		}
	}

	return linked
}
